In a number of different disciplines, such as computer-aided geometric design (CAGD), it is necessary to model, or approximate, parametric curves from sparse data. Typically, such modeling techniques attempt to model planar curves with high accuracy, while maintaining curvature continuity. In this regard, many conventional techniques model curves based upon interpolation algorithms that are based upon the notion of the curve being twice continuously differentiable with respect to arclength and capable of being constructed locally.
A planar curve f is said to be twice continuously differentiable if the unit tangent vector f*:=f′/|f′| and the signed curvature f**:=f′×f″/|f′|3 are continuous. Let fi, di and κi be prescribed positions, directions and curvature values, respectively. For example, these data might be thought to have come from a twice continuously differentiable planar curve as:fi:=f(ti), di:=f*(ti) and κi:=f**(ti)  (1)From such data, then, one such interpolation technique, known as Hermite interpolation, can determine a geometric Hermite interpolant p that satisfies:p(i)=fi, p*(i)=di and p**(i)=κi  (2)where the components of p are polynomials on each parameter interval [i, i+1]. Also, to preserve the convexity of the data, that is, to satisfy the following assumption:sign(κi)=sign(di×(fi+1−fi))=sign(fi−fi−1)×di), for all i  (3)the curvature of the interpolant typically has the same sign throughout.
As will be appreciated by those skilled in the art, many modeling, or interpolation techniques, operate to model a curve by separately interpolating different sections of the curve, where each section is defined by a set of end points. In this regard, because p can be constructed interval-by-interval, any such piecewise constructed interpolant will necessarily be continuously differentiable. Therefore, the interpolant p can be described as being constructed over the interval [0,1] without any loss of generality. According to one Hermite interpolation technique, developed by de Boor, Höllig and Sabin (referred to herein as the BHS technique), a cubic polynomial is used on each interval. Turning attention to the interval [0,1], then, the interpolant p can be written as:
                                                        p              ⁡                              (                t                )                                      =                                          ∑                                  j                  =                  0                                3                            ⁢                                                b                  j                                ⁢                                                      B                    j                                    ⁡                                      (                    t                    )                                                                                ,                                      (                      0            ≤            t            ≤            1                    )                                with      ⁢                          ⁢                        B          j                ⁡                  (          t          )                      :=                  (                                            3                                                          j                                      )            ⁢                                                  t              j                        ⁡                          (                              1                -                t                            )                                            (                          3              -              j                        )                          .            
Interpolation of position at the given knots implies thatb0=f0 and b3=f1.The remaining interpolation conditions can be simplified by introducing
      b    ~    :=                              (                                    f              1                        ×                          d              1                                )                ⁢                  d          0                    +                        (                                    d              0                        ×                          f              0                                )                ⁢                  d          1                                    d        0            ×              d        1            Geometrically, {tilde over (b)} is the intersection of the line through f0 parallel to d0, and the line through f1 parallel to d1, as shown in FIG. 1. The tangent interpolation condition is then defined as:b1=(1−ρ0)b0+ρ0{tilde over (b)} and b2=(1−ρ1)b3+ρ1{tilde over (b)}for some 0<ρ0, ρ1≦1, where ρ0 and ρ1 represent weights in writing b1 and b2 as convex combinations of b0, b3 and {tilde over (b)}. Moreover, the curvature interpolation condition is given by:
                              κ          0                =                              2            ⁢                          d              0                        ×                          (                                                b                  2                                -                                  b                  1                                            )                                            3            ⁢                                                                                                b                    1                                    -                                      b                    0                                                                              2                                                  and                                κ          1                =                                            2              ⁢                              (                                                      b                    2                                    -                                      b                    1                                                  )                            ×                              d                1                                                    3              ⁢                                                                                                            b                      3                                        -                                          b                      2                                                                                        2                                              .                    Substituting b2−b1=b2−{tilde over (b)}+{tilde over (b)}−b1=(1−ρ1)(b3−{tilde over (b)})+(1−ρ0)({tilde over (b)}−b0) into the last equations for the curvature interpolation condition, κ0 and κ1 can be determined as follows:
                                                                        κ                0                            =                                                2                  ⁢                                      (                                          1                      -                                              ρ                        1                                                              )                                    ⁢                                      d                    0                                    ×                                      (                                                                  b                        3                                            -                                              b                        ~                                                              )                                                                    3                  ⁢                                                                          ⁢                                      ρ                    0                    2                                    ⁢                                                                                                                                    b                          ~                                                -                                                  b                          0                                                                                                            2                                                                                            and                                                              κ                1                            =                                                2                  ⁢                                      (                                          1                      -                                              ρ                        0                                                              )                                    ⁢                                      (                                                                  b                        ~                                            -                                              b                        0                                                              )                                    ×                                      d                    1                                                                    3                  ⁢                                                                          ⁢                                      ρ                    1                    2                                    ⁢                                                                                                                                    b                          3                                                -                                                  b                          ~                                                                                                            2                                                                                                          (        4        )            Defining an R0 and R1 as follows:
                              R          0                :=                              3            ⁢                                                  ⁢                          κ              0                        ⁢                                                                                                b                    ~                                    -                                      b                    0                                                                              2                                            2            ⁢                          d              0                        ×                          (                                                b                  3                                -                                  b                  ~                                            )                                                  and                                R          1                :=                              3            ⁢                                                  ⁢                          κ              1                        ⁢                                                                                                b                    3                                    -                                      b                    ~                                                                              2                                            2            ⁢                          (                                                b                  ~                                -                                  b                  0                                            )                        ×                          d              1                                          and solving equation (4) for ρ0 and ρ1 gives:ρ0=1−R1ρ12 and ρ1=1−R0ρ02.
As will be appreciated by those skilled in the art, the BHS technique may have 0, 1, 2 or 3 solutions with 0<ρ0, ρ1≦1 and a sufficient condition for solvability is that (1−R0)(1−R1)≧0. With respect to techniques such as the BHS technique, it has been suggested that fi and di be prescribed first, with appropriate values for κi selected to satisfy the foregoing condition. However, such a technique of determining fi, di and κi is not always feasible since, for example, there may be predetermined values that κi must have. Also, such a condition, which in terms of the data can be represented as:(2(d0×(f1−f0))(d0×d1)2−3κ0((f1−f0)×d1)2)·(2((f1−f0)×d1)(d0×d1)2−3κ1(d0×(f1−f0))2)≧0,puts an abstruse restriction on the data. Further, ρ0 and ρ1 cannot be chosen in any manner that will make them continuous functions of the data for all admissible data sets. For example, as shown in FIG. 2, when the data changes in such a way that R1 remains constant at 0.875 while R0 increases to 0.875 (say from 0), then ρ0=0.1674 and ρ1=0.9755 when R0=R1=0.875. However, if the same data configuration is arrived at in such a way that R0 remains constant at 0.875 while R1 increases to 0.875 (say from 0), then ρ0=0.9755 and ρ1=0.1674 when R0=R1=0.875.